/*Sean Waitkus 364 Program 2  Quick Sort modification
This is my modified quick sort algorithm.  It chooses the pivot element based on the median value of three
indicies, the first, last, and (first + last)/2
formatted using eclipse

 */
public class QuickSort {
	public static void quickSort(int[] list) {
		quickSort(list, 0, list.length - 1);
	}

	private static void quickSort(int[] list, int first, int last) {
		if (last > first) {
			int pivotIndex = partition(list, first, last);
			quickSort(list, first, pivotIndex - 1);
			quickSort(list, pivotIndex + 1, last);
		}
	}

	/** Partition the array list[first..last] */
	private static int partition(int[] list, int first, int last) {
		int middle = ((first + last) / 2);
		// swap middle with first
		if (list[first] >= list[middle] && list[middle] <= list[last]
				&& list[last] <= list[first]) {// if middle is less than or
												// equal to first and last
			int tempFirst = list[first];// store first for swapping
			int tempMiddle = list[middle];// store middle for swapping
			list[first] = tempMiddle;// swap middle with first
			list[middle] = tempFirst;// swap first with middle
		}
		// swap last with first
		else if (list[first] >= list[middle] && list[middle] >= list[last]
				&& list[last] <= list[first]) {
			int tempLast = list[last];// store last for swapping
			int tempFirst = list[first];// store first for swapping
			list[first] = tempLast;// swap first with last
			list[last] = tempFirst;// wasp last with first
		}// swap middle with first
		else if (list[first] <= list[middle] && list[middle] <= list[last]
				&& list[last] >= list[first]) {
			int tempFirst = list[first];// store first for swapping
			int tempMiddle = list[middle];// store middle for swapping
			list[first] = tempMiddle;// swap middle with last
			list[middle] = tempFirst;// swap middle with last

		}// leave first

		int pivot = list[first]; // Choose the first element as the pivot
		int low = first + 1; // Index for forward search
		int high = last; // Index for backward search

		while (high > low) {
			// Search forward from left
			while (low <= high && list[low] <= pivot)
				low++;

			// Search backward from right
			while (low <= high && list[high] > pivot)
				high--;

			// Swap two elements in the list
			if (high > low) {
				int temp = list[high];
				list[high] = list[low];
				list[low] = temp;
			}
		}

		while (high > first && list[high] >= pivot)
			high--;

		// Swap pivot with list[high]
		if (pivot > list[high]) {
			list[first] = list[high];
			list[high] = pivot;
			return high;
		} else {
			return first;
		}
	}

	/** A test method */
	public static void main(String[] args) {
		int[] list = { 2, 3, 2, 5, 6, 1, -2, 3, 14, 12 };
		quickSort(list);
		for (int i = 0; i < list.length; i++)
			System.out.print(list[i] + " ");
	}
}
